#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//#include <malloc.h> //windows下用这个头文件

/*
****
    author:lwt
    date:2023/10/19
    copy reserver

    动态方式实现链表
    https://www.prepbytes.com/blog/linked-list/insert-a-node-into-the-middle-of-the-linked-list/
    https://www.geeksforgeeks.org/insert-a-node-in-linked-list-before-a-given-node/

    该版本耦合性更好，更关注核心操作
*/

typedef int ElementType;
//构造数据结构
typedef struct node{
    ElementType data;
    struct node* next;
} Node;

//op1.按位置进行查找
/*
 * 函数名findByPos
 * 功能：在带头结点的单链表list中第pos个位置插是什么元素，如果成功返回结点,否则返回NULL
 * 输入： list 链表，pos 待插入位置，element 插入元素
 * 输出  bool /int
 * */
Node *findByPos(Node *head,int pos){
    if(head==NULL || pos<1){
        return NULL;
    }
    Node *cur=head;
    int i =0;//设置计数器
    while (cur!=NULL && i< pos){
        cur=cur->next;
        i++;
    }
    if(i==pos){
        return cur;
    } else{
        return NULL;
    }
}

//op1.按位置进行查找
/*
 * 函数名findByValue
 * 功能：在带头结点的单链表list中，查找包含元素value的结点，如果成功返回结点,否则返回NULL
 * 输入： list 链表，element 查找元素
 * 输出  bool /int
 * */
Node *findByValue(Node *head,ElementType element){
    if(head==NULL ){
        return NULL;
    }
    Node *cur=head->next;
    while (cur!=NULL && cur->data != element){
        cur =cur->next;
    }

    /*
    if(cur ==NULL){
        return NULL;
    }else
        return cur;*/
    return cur;

}


//op3.插入
/*
 * 函数名insert
 * 功能：在带头结点的单链表list中第pos个位置插入元素element，如果成功返回true,否则返回false
 * 输入： list 链表，pos 待插入位置，element 插入元素
 * 输出  bool /int
 * */

bool insert(Node *head,int pos,ElementType element){
    //pre为第pos个结点的前结点，newNode为新结点，用于存储element;
    Node *pre,*newNode;
    int i=0;//变量i为计数器；

    //1. 创建新结点，用与存放元素element;
    //1.1 给结点分配空间
    newNode = malloc(sizeof (Node));
    //1.2 赋值
    newNode->data=element;

    //2 寻找pre结点
    pre=head;
    while (pre!=NULL && i<pos-1){
        pre=pre->next;
        i++;
    }
    if(pre==NULL || i>pos-1){ //i>pos-1只有pos<1的情况下出现，因此该条件处理了pos<1这种情况
        printf("插入位置错误\n");
        return false;
    }
    //3.执行插入
    //3.1 新结点链接原来位置的结点
    newNode->next=pre->next;
    //3.2 前结点链接新结点
    pre->next=newNode;
    return true;

}

//op4.删除
/*
 * 删除第pos个结点
 * 函数名delete
 * 功能：在带头结点的单链表list中,删除第第pos个位置的结点，如果成功返回true,否则返回false
 * 输入： list 链表，pos 待删除位置
 * 输出  bool /int
 * */
bool delete(Node *head,int pos){

    //找到第pos个结点的前结点
    //1.声明
    Node *pre;
    int i=0;//定义计数器变量i
    // 2.找前结点
    pre =head;
    while(pre->next!=NULL && i <pos-1){ //注意，pre.next为待删除结点，因此不为空才有删除的意义
        pre=pre->next;
        i++;
    }
    if(pre->next==NULL || i> pos-1){
        printf("插入位置错误\n");
        return false;
    }
    //3. 执行删除，释放结点
    Node *cur;
    cur=pre->next;
    pre->next=cur->next;
    free(cur);//释放结点
    return true;

}


int main() {

    //手动链接结点，进行测试
    //1.构造多个节点
        // 1.1 声明结点
    Node *head,*first,*second,*third;

        //1.2 给指针分配空间
    head = malloc(sizeof(Node));
    first = malloc(sizeof(Node));
    second = malloc(sizeof(Node));
    third = malloc(sizeof(Node*));


    //2 将数据放入到结点中
    first->data=1;
    second->data=2;
    third->data=3;

    //3.链接成链表
    head->next=first;
    first->next=second;
    second->next=third;
    third->next=NULL;

    //1 根据位置查找
    Node *node1= findByPos(head,2);


    //2 根据元素查找
    Node *node2= findByValue(head,3);

    // 3. 测试插入
    insert(head,2,5);

    // 4. 测试删除
    delete(head,3);


    return 0;
}
